package com.arron.algorithm.leetcodetop100.回溯.岛屿;

/**
 *
 *  优秀题解： https://leetcode.cn/problems/word-search/solutions/2361646/79-dan-ci-sou-suo-hui-su-qing-xi-tu-jie-5yui2/?envType=study-plan-v2&envId=top-100-liked
 *
 */
public class 单词搜索 {


    int[][] flag;

    public boolean exist(char[][] board, String word) {

        flag = new int[board.length][board[0].length];

        int m = board.length;
        int n = board[0].length;
        char[] chars = word.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, chars, 0, i,j )){
                    return true;
                }
            }

        }

        return false;
    }

    public boolean dfs(char[][] board, char[] word, int index, int i, int j) {

        if (i < 0 || i >= board.length) {
            return false;
        }

        if (j < 0 || j >= board[0].length) {
            return false;
        }
        if (word[index] != board[i][j]) {
            return false;
        }
        //已经访问过的直接返回
        if (flag[i][j] !=0){
            return false;
        }


        //最后一个字符已经匹配则直接返回true
        if (index + 1 == word.length) {
            return true;
        }
        //更加高效率的做法是，直接修改 board[i][j] = '\0' ，在回溯完之后再修改回去 board[i][j] = word[index]
        flag[i][j] = 1;
        //去上边，下边，左边，右边，
        boolean res = dfs(board, word, index+1, i - 1, j) || dfs(board, word,index+1, i + 1, j)
                || dfs(board, word, index+1, i, j - 1) || dfs(board, word, index+1, i, j + 1);
        //当前的所有路径中回缩结束后要全部还原
        flag[i][j] = 0;
        return res;
    }


    public static void main(String[] args) {
        单词搜索 wordSearch = new 单词搜索();

        char[][] dict = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};

        String word = "ABCCED";
        wordSearch.exist(dict, word);
    }

}
